import java.util.ArrayList;
import java.util.List;

/**
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则输出Yes,否则输出No。
 * 假设输入的数组的任意两个数字都互不相同。
 */
public class Solution33 {
    public boolean VerifySquenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }

        return verifySquenceOfBST(sequence);
    }

    private boolean verifySquenceOfBST(int[] sequence) {
        if (sequence.length == 1 || sequence.length == 0) {
            return true;
        }

        int root = sequence[sequence.length - 1];

        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();

        boolean noLeft = false;

        for (int i = 0; i < sequence.length - 1; i++) {
            if (noLeft) {
                right.add(sequence[i]);
            } else {
                if (sequence[i] < root) {
                    left.add(sequence[i]);
                } else {
                    noLeft = true;
                    right.add(sequence[i]);
                }
            }
        }

        int[] left2 = new int[left.size()];
        int[] right2 = new int[right.size()];

        for (int i = 0; i < left.size(); i++) {
            if (left.get(i) > root) {
                return false;
            }
            left2[i] = left.get(i);
        }

        for (int i = 0; i < right.size(); i++) {
            if (right.get(i) < root) {
                return false;
            }
            right2[i] = right.get(i);
        }

        return verifySquenceOfBST(left2) && verifySquenceOfBST(right2);
    }
}
